from functools import cache


class Solution:
    def stringCount(self, n: int) -> int:

        @cache
        def f(i, l, e, t):
            if i == n:
                return int(l > 0 and e > 1 and t > 0)
            ans = 0
            for k in range(26):
                ans += f(
                    i + 1,
                    min(1, l + int(k == 0)),
                    min(2, e + int(k == 1)),
                    min(1, t + int(k == 2)),
                )
                ans %= 1000000007
            return ans

        return f(0, 0, 0, 0)


class Solution:
    def stringCount(self, n: int) -> int:

        @cache
        def f(i, l, e, t):
            if i == 0:
                return int(l == e == t == 0)
            if l == 0 and e == 0 and t == 0:
                return pow(26, i, 1000000007)
            ans = 23 * f(i - 1, l, e, t)
            ans += f(i - 1, 0, e, t)
            ans += f(i - 1, l, max(e - 1, 0), t)
            ans += f(i - 1, l, e, 0)
            # for k in range(26):
            #     ans += f(i + 1, l + int(k == 0), e + int(k == 1), t + int(k == 2))
            ans %= 1000000007
            return ans

        return f(n, 1, 2, 1)


@cache
def dfs(i: int, L: int, t: int, e: int) -> int:
    if i == 0:
        return 1 if L == t == e == 0 else 0
    res = dfs(i - 1, 0, t, e)  # 选 l
    res += dfs(i - 1, L, 0, e)  # 选 t
    res += dfs(i - 1, L, t, max(e - 1, 0))  # 选 e
    res += dfs(i - 1, L, t, e) * 23  # 其它字母
    return res % (10**9 + 7)


class Solution:
    def stringCount(self, n: int) -> int:
        return dfs(n, 1, 1, 2)


s = Solution()
print(s.stringCount(4))
print(s.stringCount(10))
print(s.stringCount(100000))
